#include"bitmap.h"
#include"stdlib.h"
#include"stdio.h"

//将ListItem作为静态变量管理
const int ListItem_SIZE = 100000; //大小
ListItem ListItem_SET[ListItem_SIZE];   //集合
bool ListItem_STATUS[ListItem_SIZE];    //分配状态
ListItem* getListItem(int start=0,int size=0)
{
    int index=-1;
    for(int i=0;i<ListItem_SIZE;i++)
    {
        if(ListItem_STATUS[i]==false)
        {
            index=i;
            ListItem_STATUS[i]=true;
            break;
        }
    }
    if(index==-1)
    {
        printf("ListItem Size not enough...\n");
        return nullptr;
    }
    ListItem* item=&ListItem_SET[index];
    item->start=start;
    item->size=size;
    item->previous=item->next=nullptr;
    return item;
}
void releaseListItem(ListItem* item)
{
    if(item==nullptr)return;
    for(int i=0;i<ListItem_SIZE;i++)
    {
        if(item==&ListItem_SET[i])
        {
            ListItem_STATUS[i]=false;
            ListItem_SET[i]=ListItem();
            break;
        }
    }
}

Bitmap::Bitmap(){}
void Bitmap::initialize(char* bitmap,const int length)
{
    this->bitmap = bitmap;
    this->length = length;
    int bytes = ceil(length,8);
    for(int i=0; i<bytes; i++)
    {
        bitmap[i] = 0;
    }
    for(int i=0;i<ListItem_SIZE;i++)
    {
        ListItem_SET[i]=ListItem();
        ListItem_STATUS[i]=false;
    }
    ListItem* item=getListItem(0,length);
    idlePartitions.push_back(item);
}
bool Bitmap::get(const int index) const
{
    int pos = index/8;
    int offset = index%8;
    return (bitmap[pos]&(1<<offset));
}
void Bitmap::set(const int index,const bool status)
{
    int pos=index/8;
    int offset=index%8;
    //清零
    bitmap[pos]=bitmap[pos]&(~(1<<offset));
    //置一
    if(status)
    {
        bitmap[pos]=bitmap[pos] | (1<<offset);
    }
}
int Bitmap::allocate(const int count)
{
    if(count==0)return -1;
    int index=0,empty,start;
    while(index<length)
    {
        //越过已经分配的资源
        while(index<length && get(index))index++;
        //不存在连续的count个资源
        if(index==length) return -1;
        //找到1个未分配的资源，检查是否为index开始的连续count个资源
        empty=0;
        start=index;
        while((index<length)&&(!get(index))&&(empty<count))
        {
            empty++;
            index++;
        }
        //存在连续个count个资源
        if(empty==count)
        {
            for(int i=0;i<count;i++)
            {
                set(start+i,true);
            }
            return start;
        }
    }
    return -1;
}
int Bitmap::allocate_best_fit(const int count)
{
    if(count==0) return -1;
    ListItem* item=nullptr;
    bool flag=false;//表示第一次找到
    for (ListItem* temp = idlePartitions.front(); temp != nullptr; temp = temp->next) {
        if (temp->size >= count) {
            if(flag==false)
            {
                flag=true;
                item=temp;
            }
            if(temp->size < item->size)item=temp;
        }
    }
    if(item!=nullptr)
    {
        int start=item->start;
        //分配资源
        for(int i=0;i<count;i++)
        {
            set(start+i,true);
        }
        //链表调整
        if(item->size==count)
        {
            idlePartitions.erase(item);
            releaseListItem(item);            
        }else{
            item->start += count;
            item->size -= count;
        }
        return start;
    }
    return -1;
}
void Bitmap::release(const int index,const int count)
{
    if(count==0)return;
    for(int i=0; i<count; i++)
    {
        set(index+i,false);
    }
    return;//first fit算法使用
    //恢复空闲分区
    int pos=idlePartitions.find_start(index+count);//地址末尾
    ListItem* item=idlePartitions.at(pos);
    ListItem* prev=nullptr;
    ListItem* next=item;
    for(ListItem* temp=idlePartitions.front();temp!=nullptr;temp=temp->next)
    {
        if(temp->start+temp->size==index)
        {
            prev=temp;
            break;
        }
    }
    //合并前后
    if(prev && next)
    {
        prev->size += count+next->size;
        idlePartitions.erase(next);
        releaseListItem(next);
    }else if(prev){
        // prev->size += count;
    }else if(next){
        next->start=index;
        next->size += count;
    }else{
        ListItem* newItem=getListItem(index,count);
        idlePartitions.insert_start(newItem);
        printf(" %d %d %d ",newItem,newItem->start,newItem->size);
        printf(" %d  %d %d\n",nullptr,newItem->previous,newItem->next);
    }
    printf("index %d count %d size %d\n",index,count,idlePartitions.size());
}
char* Bitmap::getBitmap()
{
    return (char*)bitmap;
}
int Bitmap::size() const
{
    return length;
}